A binary tree is a data structure with a finite set of nodes consisting of:
- A unique node with no parents called root and zero or more subtrees.
- Every node can be connected to an arbitrary number of nodes, called children.
- Nodes with no children are called external nodes or leaves.
- Internal nodes are the ones that they are not leaves.
- The Nodes that have the same parent are called siblings.
- The top node is called the root with no parent-child.
- The last nodes with no further child nodes are called leaves.
Binary Tree in C++
Tree traversals
Tree traversal refers to visiting each node only once.
Post-order traversal – It visits the left child, then the right child and then the parent
In-order traversal – It visits the left child, then the parent and the right child
Level-order traversal – it visits nodes by levels from top to bottom and from left to right
Structure of the Tree Node in C++
struct node { int key; node* left, *right; };
Create a new node in a Binary tree using C++
The following function will create a new node in the Binary Tree
struct node* newnode(int key) { struct node* temp = new node; temp->key = key; temp->left = temp->right = NULL; return temp; };
Now call the function above to add a new node:
node* root = newnode(5); root->left = newnode(6); root->left->left = newnode(4); root->right = newnode(2); root->right->left = newnode(3); root->right->right = newnode(7);
In-Order Traversal
Let’s traverse Binary Tree using in-order traversal
void inorder(node* temp) { if (temp == NULL) return; inorder(temp->left); cout << temp->key << " "; inorder(temp->right); }
To display tree in in-order traversal order, call
inorder(root);
Pre-Order Traversal
Let’s traverse Binary Tree using pre-order traversal
void preorder(node* temp) { if (temp == NULL) return; cout << temp->key << " "; preorder(temp->left); preorder(temp->right); }
To display tree in pre-order traversal order, call
preorder(root);
Post-Order Traversal
Let’s traverse Binary Tree using post-order traversal
void postorder(node* temp) { if (temp == NULL) return; postorder(temp->left); postorder(temp->right); cout << temp->key << " "; }
To display tree in post-order traversal order, call
postorder(root);
Level-Order Traversal
Let’s traverse Binary Tree using level-order traversal
To traverse level-order, you need to find the level of the node you are visiting.
void levelorder(node* root) { int h = height(root); int i; for (i = 1; i <= h; i++) letlevelorder(root, i); } void letlevelorder(node* root, int level) { if (root == NULL) return; if (level == 1) cout << root->key << " "; else if (level > 1) { letlevelorder(root->left, level-1); letlevelorder(root->right, level-1); } } int height(node* node) { if (node == NULL) return 0; else { /* compute the height of each subtree */ int lheight = height(node->left); int rheight = height(node->right); /* use the larger one */ if (lheight > rheight) return(lheight + 1); else return(rheight + 1); } }
Traversing trees using all four methods
int main() { node* root = newnode(5); root->left = newnode(6); root->left->left = newnode(4); root->right = newnode(2); root->right->left = newnode(3); root->right->right = newnode(7); cout<<"Pre-order Traversal: "; preorder(root); cout<<endl; cout<<"Post-order Traversal: "; postorder(root); cout<<endl; cout<<"In-order Traversal: "; inorder(root); cout<<endl; cout<<"Level-order Traversal: "; levelorder(root); cout<<endl; return 0; }